class NodeNotFoundErorr(LookupError):
    pass


class Tree:
    # 初始化
    def __init__(self, *, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    # 打印某个节点的信息
    def __repr__(self):
        return "Tree(val={}, left={}, right={})".format(self.val, self.left, self.right)

    # 判断一个节点是否是叶子节点
    def is_leaf(self):
        return self.left is None and self.right is None

    # 查找子节点
    def find(self, val):
        if self.val == val:
            return self
        elif val < self.val and self.left is not None and self.left.find(val):
            return self.left.find(val)
        elif val > self.val and self.right is not None and self.right.find(val):
            return self.right.find(val)

    # 判断某个节点是否存在
    def exists(self, val):
        return bool(self.find(val))

    # 查找子节点  没有找到就抛出异常
    def findstrict(self, val):
        found = self.find(val)

        if found:
            return found
        else:
            raise NodeNotFoundErorr("node '{}' not found".format(val))

    # 增加子节点
    def add(self, val):
        if val < self.val:
            if self.left is None:
                self.left = Tree(val=val)
            else:
                self.left.add(val)
        else:
            if self.right is None:
                self.right = Tree(val=val)
            else:
                self.right.add(val)

    # 前序遍历
    def preorder_traversal(self):
        """root left right"""
        result = [self.val]

        if self.left is not None:
            result.extend(self.left.preorder_traversal())
        if self.right is not None:
            result.extend(self.right.preorder_traversal())

        return result

    # 中序遍历
    def inorder_traversal(self):
        """left root right"""
        result = []

        if self.left is not None:
            result.extend(self.left.inorder_traversal())
        result.append(self.val)
        if self.right is not None:
            result.extend(self.right.inorder_traversal())

        return result

    sort = inorder_traversal

    # 后序遍历
    def postorder_traversal(self):
        """left right root"""
        result = []

        if self.left is not None:
            result.extend(self.left.postorder_traversal())
        if self.right is not None:
            result.extend(self.right.postorder_traversal())
        result.append(self.val)

        return result

    # 层序遍历
    def level_traversal(self):
        result = []
        self._level_helper(self, 0, result)
        # return [n for row in result for n in row]
        return result

    def _level_helper(self, root, level, result):
        if root is None:
            return
        if len(result) <= level:
            result.append([])
        result[level].append(root.val)
        self._level_helper(root.left, level + 1, result)
        self._level_helper(root.right, level + 1, result)


# tree = Tree(val=2, left=Tree(val=1), right=Tree(val=3))
# print(tree.find(4))  # returns None if the node is not found
# print(tree.findstrict(4))  # raises a error if the node is not found
# tree.add(4)
# print(tree.find(4))
# print(tree.findstrict(4))

tree = Tree(val=5)
for node in [3, 7, 2, 4, 6, 8]:
    tree.add(node)

print(tree.level_traversal())
